(*
parties : 'a list -> 'a list list
Paramètres : l - une liste quelconque d'éléments
Résultat : une liste de listes, dont les 2^(List.length l) éléments
sont les sous-listes de l.
Si les éléments de l sont différents, les listes éléments du résultat
seront différentes aussi, et formeront les parties de l.
*)
Exercice 1 : Donner une formulation récursive comptant le nombre de parties d’un ensemble de cardinal n.
[] -> [] 1 partie
[e1] -> [e1],[] 2 parties (soit je prend e1, soit je ne le prends pas)
[e1,e2] -> [e1,e2],[e1],[e2],[] 4 parties (je peux prendre e2 ou non pour l'ajouter aux parties calculées au niveau n-1)
Ainsi, n éléments -> 2^n parties
Exercice 2 :
ajout, qui à partir d’un élément et d’ensembles renvoie l’enemble .(*
Contrat ajout : 'a -> 'a list list -> 'a list list
Paramètres :
- e : 'a - élément à ajouter à chaque ensemble
- parties : 'a list list - liste des parties
Résultat : 'a list list -
liste des parties en ayant pris en compte l'ajout de l'élément e
*)
let ajout e parties = List.flatten (List.map (fun p -> [p;e::p]) parties)
(* OU *)
let ajout e parties = parties@(List.map (fun p -> e::p) parties)
parties, qui renvoie l’ensemble des parties d’un ensemble.(*
Contrat parties : 'a list -> 'a list list
Paramètres :
- l : 'a list - un ensemble
Résultat : 'a list list - parties de l'ensemble l
*)
let rec parties l =
match l with
| [] -> [[]]
| e::r -> ajout e (parties r)
(* OU *)
let parties l = fold_right ajout l [[]]
(*
permutations : 'a list -> 'a list list
Paramètres : l - une liste quelconque d'éléments
Résultat : une liste de listes, dont les (List.length l)! éléments ont la même
longueur que l. Si les éléments de l sont différents, les listes éléments du
résultat seront différentes aussi, et formeront les permutations de l.
*)
Exercice 3 : Donner une formulation récursive comptant le nombre de permutations d’un ensemble de taille n.
[] -> [] 1 permutation
[e1] -> [e1] 1 permutation
[e1;e2] -> [e1;e2],[e2;e1] 2 permutations (on a inséré e2 à toutes les positions possibles)
[e1;e2;e3] -> [e3;e1;e2],[e1;e3;e2],[e1;e2;e3], 6 permutations (on a inséré e3 à toutes les positions possibles pour chaque ensemble du niveau précédent)
[e3;e2;e1],[e2;e3;e1],[e2;e1;e3]
Exercice 4 :
insertions, qui insère un élément à toutes les positions d’une liste.(*
Contrat insertions : 'a -> 'a list -> 'a list list -
Insère l'élément à toutes les possitions possibles de l
Paramètres :
- e : 'a - élément à insérer
- l : 'a list
Résultat : 'a list list -
liste de toutes les possibilités d'insertion de e dans l
*)
let rec insertions e l =
match l with
| [] -> [[e]]
| t::q -> (e::l) :: (List.map (fun x -> t::x) (insertions e q))
permutations, qui renvoie l’ensemble des permutations d’un ensemble.(*
Contrat permutations : 'a list -> 'a list list -
Calcule toutes les permutations d'un ensemble
Paramètres :
- l : 'a list - l'ensemble dont on va calculer les permutations
Résultat : 'a list list - Ensemble des permutations de l
*)
let rec permutations l =
match l with
| [] -> [[]]
| t::q -> List.flatten (List.map (fun x -> insertions t x) (permutations q))
(*
combinaisons : 'a list -> int -> 'a list list
Paramètres :
- l : 'a list - une liste quelconque d'éléments supposés différents
- k : int - le nombre d'éléments distincts à tirer
Résultat : une liste de combinaisons. Chaque combinaison est elle-même une liste
d'éléments, dont les éléments sont ceux de l.
*)
Exercice 5 : Donner une formulation récursive comptant le nombre de combinaisons de k éléments d’un ensemble à n éléments.
C(k,0) = 1 -> [[]]
C(0,n) = 0 -> []
C(k,n) = C(k-1,n-1) + C(k,n-1) -> soit je prend le nouvel élément, soit je ne le prend pas
Exercice 6 : Ecrire la fonction combinaisons (contrat + code + tests).
(*
Contrat combinaisons : 'a list -> int -> 'a list list -
Calcule toutes les combinaisons de k éléments d'un ensemble à n éléments
Paramètres :
- l : 'a list - ensemble des éléments
- k : int - nombre d'éléments dont on veut calculer les combinaisons
Résultat : 'a list list - Toutes les parties de l à k éléments
*)
let rec combinaisons l k =
match (l,k) with
| (_,0) -> [[]]
| ([],_) -> []
| (t::q,_) -> (List.map (fun x -> t::x) (combinaisons q (k-1))) @ (combinaisons q k)
let%test _ = combinaisons ['c';'a';'c';'a'] 0 = [[]]
let%test _ = combinaisons [] 69 = []
let%test _ = combinaisons ['t';'g'] 1 = [['t'];['g']]
let%test _ = combinaisons ['f';'t';'g'] 2 = [['f';'t'];['f';'g'];['t';'g']]